\documentclass[utf8]{ctexart}

\usepackage[a4paper,left=1.25in,right=1.25in,top=1in,bottom=1in]{geometry}
\usepackage{listings}
\usepackage{graphicx}
\usepackage{subfigure}
\usepackage{booktabs}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{float}
\usepackage{indentfirst}
\usepackage{gnuplot-lua-tikz}
\usepackage{tikz}
\usetikzlibrary{shapes,arrows}
\usetikzlibrary{shapes.geometric, arrows}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{newclude}
\usepackage[perpage]{footmisc}

\graphicspath{ {images/} }
\raggedbottom	% 令页面在垂直方向向顶部对齐
\renewcommand\qedsymbol{QED}
\renewcommand{\figurename}{Figure}
\renewcommand{\proofname}{Proof}
\newcommand{\sign}[1]{\mathrm{sgn}(#1)}
\everymath{\displaystyle}   % 行内公式采用行间公式格式排列

\title{Theoretical Questions 3}
\author{Yin Wenliang\qquad 3200101893}
\date{}

\begin{document}
\maketitle
\CTEXsetup[format={\Large\bfseries}]{section}

\begin{enumerate}
\item
  % 问题1
  \textbf{Solution}\par
  Notice that
  \begin{equation*}
    p(0) = 0,p(1) = 1,p'(1) = -3,p''(1) = 6.
  \end{equation*}
  Then we have
  \begin{align*}
    p(x) &= p(1) + p'(1)(x-1) + \frac{p''(1)}{2}(x-1)^2 + \frac{p^{(3)}(1)}{3!}(x-1)^3\\
    &= 1- 3(x-1) + 3(x-1)^2 + a(x-1)^3.
  \end{align*}
  where $a=\frac{p^{(3)}(1)}{3!}$.\par
  Substituting the condition $s(0)=p(0)=0$ yields
  \begin{equation*}
    0 = 1 - (-3) + 3 - a \implies  a = 7.
  \end{equation*}
  Hence
  \begin{align*}
    p(x) &= 1 - 3(x-1) + 3(x-1)^2 + 7(x-1)^3\\
    &= 7x^3 - 18x^2 + 12x
  \end{align*}
  Observe that $s''(0) = p''(0) = -36\ne 0$, so $s(x)$ is not a natural cubic spline.
\item
  % 问题2
  \textbf{Solution}\par
  \begin{enumerate}
  \item
    By Theorem 3.14, the dimension of $\mathbb{S}_2^1$ is $n+1$. Apart from the $n$ interpolation conditions at $x_1,x_2,\cdots,x_n$, an additional condition is needed to determine $s$ uniquely.
  \item
    We construct the following table of divided difference.
    \begin{table}[H]
      \centering
      \begin{tabular}{c|ccc}
        $x_i$ & $f_i$\\
        $x_i$ & $f_i$ & $m_i$\\
        $x_{i+1}$ & $f_{i+1}$ & $K_i$ & $\frac{K_i-m_i}{x_{i+1}-x_i}$ 
      \end{tabular}
    \end{table}
    where $K_i=f[x_i,x_{i+1}]$.\par
    Then the Newton formula yields
    \begin{equation*}
      p_{i}(x) = f_i + (x-x_i)m_i + (x-x_i)^2\frac{K_i-m_i}{x_{i+1}-x_i}.
    \end{equation*}
  \item
    By (b), $s'_{i-1}(x_i) = s'_{i}(x_i)$ implies that
    \begin{equation*}
      m_{i-1}+m_i = 2f[x_{i-1},x_{i}].
    \end{equation*}
    Hence $m_2,m_3,\cdots,m_{n-1}$ can be attained by
    \begin{equation*}
      m_i = 2f[x_{i-1},x_i] -m_{i-1},\quad i = 2,3,\cdots,n-1
    \end{equation*}
    where $m_1=f'(a)$.
  \end{enumerate}
  
\item
  % 问题3
  \textbf{Solution}\par
  Notice that $s_1(0)=s_2(0)=1+c,s_2'(0)=s_1'(0)=3c,s"_1(0)=s"_2(0)=6c$, and natual cubic spline condition implies $s"(1)=0$.\par
  By Taylor formula, we have
  \begin{align*}
    s_2(x) &= s_2(0) + xs'_2(0)+\frac{x^2}{2}s"_2(0)+ax^3\\
    &= ax^3 + 3cx^2+3cx+c+1.
  \end{align*}
  Substituting the condition $s"_2(1)=0$ yields
  \begin{equation*}
    s"_2(1) = 6a + 6c = 0 \implies a = -c
  \end{equation*}
  Hence
  \begin{equation*}
    s_2(x) = -cx^3+3cx^2+3cx+c+1,\quad x\in[0,1].
  \end{equation*}
  If $s(1)=-1$ holds, then
  \begin{equation*}
    s_2(1) = -c+3c+3c+c+1=-1 \implies c=-\frac{1}{3}.
  \end{equation*}
  So $c=-\frac{1}{3}$.
\item
  % 问题4
  \textbf{Solution}\par
  \begin{enumerate}
  \item
    For $s_1$ in $[-1,0]$ and $s_2$ in $[0,1]$, observe that
    \begin{align*}
      s_1(-1) = \cos{(-\frac{\pi}{2})} = 0,\\
      s_1(0)=s_2(0)=\cos{0}=1,s_1'(0)=s_2'(0),s_1"(0)=s_2"(0),\\
      s_2(1)=\cos{\frac{\pi}{2}}=0.
    \end{align*}
    Then by Taylor formula and the natural cubic spline condition, we have
    \begin{align*}
      s_1(x) &= s_1(-1)+a(x+1)+\frac{s_1"(-1)}{2}(x+1)^2+b(x+1)^3\\
      &= b(x+1)^3+a(x+1),\quad x\in[-1,1]
    \end{align*}
    and
    \begin{align*}
      s_2(x) &= s_2(1)+c(x-1)+\frac{s"_2(1)}{2}(x-1)^2+d(x-1)^3\\
      &= d(x-1)^3 + c(x-1),\quad x\in[0,1]
    \end{align*}
    where $a=s_1'(-1),b=s_1^{(3)}(-1),c=s_2'(1),d=s_2^{(3)}(1)$.\par
    Use conditions $s_1(0)=s_2(0)=1,s_1'(0)=s_2'(0),s_1"(0)=s_2"(0)$, we have
    \begin{equation*}
      \begin{cases}
        a + b &= 1\\
        -c -d &= 1\\
        a + 3b &= c + 3d\\
        6b &= -6d
      \end{cases}
      \implies
      \begin{cases}
        a &= \frac{3}{2}\\
        b &= -\frac{1}{2}\\
        c &= -\frac{3}{2}\\
        d &= \frac{1}{2}
        \end{cases}
    \end{equation*}
    Hence
    \begin{align*}
      s_1(x) &= -\frac{1}{2}(x+1)^3+\frac{3}{2}(x+1)\\
      &= -\frac{1}{2}x^3-\frac{3}{2}x^2+1,\quad x\in[-1,0],\\
      s_2(x) &= \frac{1}{2}(x-1)^3-\frac{3}{2}(x-1)\\
      &= \frac{1}{2}x^3-\frac{3}{2}x^2+1,\quad x\in[0,1].
    \end{align*}
  \item
    For the first case that $g(x)$ is a quadratic polynomial, construct the table of divided difference as follows.
    \begin{table}[H]
      \centering
      \begin{tabular}{c|ccc}
        -1 & 0\\
        0 & 1 & 1\\
        1 & 0 & -1 & -1
        \end{tabular}
    \end{table}
    So $g(x) = -x^2+1$, and we have
    \begin{equation*}
      E_1 = \int_{-1}^{1}[g"(x)]^2dx = 8.
    \end{equation*}
    For the second case that $g(x)$ is equal to $f(x)$,
    \begin{equation*}
     f"(x)= \begin{cases}
       -3x-3,\quad x\in[-1,0],\\
       3x-3,\quad x\in[0,1],
        \end{cases}
    \end{equation*}
    thus
    \begin{equation*}
      E_2 = \int_{-1}^0(-3x-3)^2dx + \int_{0}^1(3x-3)^2dx = 6 < E_1,
    \end{equation*}
    which completes the verification.
    \end{enumerate}
  \item
    % 问题5
    \textbf{Solution}\par
    \begin{enumerate}
      \item
    By Example 3.24 and Definition 3.21, we recall that
    \begin{equation*}
      B_i^1(x)=
      \begin{cases}
        \frac{x-t_{i-1}}{t_i-t_{i-1}}\quad &x\in(t_{i-1},ti],\\
          \frac{t_{i+1}-x}{t_{i+1}-t_i}\quad &x\in(t_i,t_{i+1}],\\
            0\quad &\text{otherwise}.
      \end{cases}      
    \end{equation*}
    Apply Definition 3.23, we have
    \begin{align*}
      B_i^2(x) &= \frac{x-t_{i-1}}{t_{i+1}-t_{i-1}}B_i^1(x)+\frac{t_{i+2}-x}{t_{i+2}-t_i}B_{i+1}^1(x)\\
      &= \begin{cases}
        \frac{(x-t_{i-1})^2}{(t_{i+1}-t_{i-1})(t_i-t_{i-1})},\qquad &x\in(t_{i-1},t_i];\\
          \frac{(x-t_{i-1})(t_{i+1}-x)}{(t_{i+1}-t_{i-1})(t_{i+1}-t_i)}+\frac{(t_{i+2}-x)(x-t_i)}{(t_{i+2}-t_i)(t_{i+1}-t_i)},\qquad &x\in(t_i,t_{i+1}];\\
            \frac{(t_{i+2}-x)^2}{(t_{i+2}-t_i)(t_{i+2}-t_{i+1})},\qquad &x\in (t_{i+1},t_{i+2}];\\
              0,\qquad &\text{otherwise}.
      \end{cases}      
    \end{align*}
  \item
    Differentiating explicit expressions of $B_i^2(x)$ given in (a) yields
    \begin{equation*}
      \frac{d}{dx}B_i^2(x)=
      \begin{cases}
        \frac{2(x-t_{i-1})}{(t_{i+1}-t_{i-1})(t_i-t_{i-1})},\qquad &x\in(t_{i-1},t_i];\\
          \frac{-2x+t_{i+1}+t_{i-1}}{(t_{i+1}-t_{i-1})(t_{i+1}-t_i)}+\frac{-2x+t_{i+2}+t_i}{(t_{i+2}-t_i)(t_{i+1}-t_i)},\qquad &x\in(t_i,t_{i+1}];\\
            \frac{-2(t_{i+2}-x)}{(t_{i+2}-t_i)(t_{i+2}-t_{i+1})},\qquad &x\in (t_{i+1},t_{i+2}];\\
              0,\qquad &\text{otherwise}.
      \end{cases}      
    \end{equation*}
    Then we have
    \begin{align*}
      \frac{d}{dx}B_i^2(t_i^-) &= \frac{2}{t_{i+1}-t_{i-1}}=\frac{d}{dx}B_i^2(t_i^+),\\
      \frac{d}{dx}B_i^2(t_{i+1}^-) &= \frac{-2}{t_{i+2}-t_i}=\frac{d}{dx}B_i^2(t_{i+1}^+)
    \end{align*}
    which verifies that $\frac{d}{dx}B_i^2(x)$ is continuous at $t_i$ and $t_{i+1}$.
  \item
    Since $\frac{d}{dx}B_i^2(x)>0$ clearly holds for each $x\in(t_{i-1},t_i]$, we pay attention to to the interval $(t_i,t_{i+1})$. Notice that $\frac{d}{dx}B_i^2(x)$ is linear in $(t_i,t_{i+1})$, an $\frac{d}{dx}B_i^2(t_i)>0$, $\frac{d}{dx}B_i^2(t_{i+1})<0$. Therefore there exists only one $x^*\in (t_{i-1},t_{i+1})$ such that $\frac{d}{dx}B_i^2(x^*)=0$.\par
      Let $\frac{d}{dx}B_i^2(x^*)=0$, we get
      \begin{equation*}
        x^* = \frac{t_{i+2}t_{i+1}-t_it_{i-1}}{t_{i+2}+t_{i+1}-t_i-t_{i-1}}.
      \end{equation*}
    \item
      By (b) and (c), we have
      \begin{align*}
        \frac{d}{dx}B_i^2(x) > 0,\quad &x\in(t_{i-1},x^*),\\
        \frac{d}{dx}B_i^2(x)<0,\quad &x\in (x^*,t_{i+2}).
      \end{align*}
      And we can easily get
      \begin{equation*}
        B_i^2(x^*) = \frac{t_{i+2}-t_{i-1}}{t_{i+2}-t_{i-1}+(t_{i+1}-t_i)}. 
      \end{equation*}
      Considering the fact that the support of $B_i^2(x)$ is $[t_{i-1},t_{i+2}]$ by Lemma 3.27, we complete the proof.
    \item
      The plotting result is illustrated in Figue \ref{fig1}.
      \begin{figure}[H]
  \centering
  \includegraphics[width=0.578\textwidth,height=0.458\textwidth]{3_0.png}
  \caption{$B_1^2(x)$}
  \label{fig1}
      \end{figure}
    \end{enumerate}
  \item
    % 问题6
    \begin{proof}
      By Theorem 2.17, we have
\begin{align*}
  &(t_{i+2} - t_{i-1})[t_{i-1},t_i,t_{i+1},t_{i+2}](t - x)_+^2\\
  &=[t_i,t_{i+1},t_{i+2}](t - x)_+^2 - [t_{i-1},t_i,t_{i+1}](t -
    x)_+^2\\
  &=\frac{[t_{i+1},t_{i+2}](t - x)_+^2-[t_i,t_{i+1}](t -
    x)_+^2}{t_{i+2} - t_{i}} -\frac{[t_i,t_{i+1}](t - x)_+^2 - [t_{i-1},t_i](t -
     x)_+^2}{t_{i+1}-t_{i-1}}\\
  &=\frac{(t_{i+2}-x)_+^2-(t_{i+1}-x)_+^2}{(t_{i+2} - t_{i})(t_{i+2} -
    t_{i+1})}-\frac{(t_{i+1}-x)_+^2-(t_{i}-x)_+^2}{(t_{i+2} -
    t_{i})(t_{i+1} - t_{i})}\\
  &\ -\frac{(t_{i+1}-x)_+^2-(t_{i}-x)_+^2}{(t_{i+1} - t_{i-1})(t_{i+1} -
    t_{i})}+\frac{(t_{i}-x)_+^2-(t_{i-1}-x)_+^2}{(t_{i+1} - t_{i-1})(t_{i} -
    t_{i-1})}.
\end{align*}
When $x\in(-\infty,t_{i-1}]$, the fact that $(t_{i-1}-x)_+^2 = (t_{i-1}-x)^2,
(t_{i}-x)_+^2 = (t_{i}-x)^2, (t_{i+1}-x)_+^2 = (t_{i+1}-x)^2$ and
$(t_{i+2}-x)_+^2 = (t_{i+2}-x)^2$ imply
\begin{align*}
  &(t_{i+2} - t_{i-1})[t_{i-1},t_i,t_{i+1},t_{i+2}](t - x)_+^2\\
  &=\frac{(t_{i+2}-x)^2-(t_{i+1}-x)^2}{(t_{i+2} - t_{i})(t_{i+2} -
    t_{i+1})} -\frac{(t_{i+1}-x)^2-(t_{i}-x)^2}{(t_{i+2} -
    t_{i})(t_{i+1} - t_{i})}\\
  &\ -\frac{(t_{i+1}-x)^2-(t_{i}-x)^2}{(t_{i+1} - t_{i-1})(t_{i+1} -
    t_{i})} +\frac{(t_{i}-x)^2-(t_{i-1}-x)^2}{(t_{i+1} - t_{i-1})(t_{i} -
    t_{i-1})}\\
  &= \frac{t_{i+2}+t_{i+1}+2x}{t_{i+2}-t_{i}} -
    \frac{t_{i+1}+t_{i}+2x}{t_{i+2}-t_{i}}\\
  &\ -\frac{t_{i+1}+t_{i}+2x}{t_{i+1}-t_{i-1}}  +\frac{t_{i}+t_{i-1}+2x}{t_{i+1} - t_{i-1}}\\
  &= 0 = B_i^2(x), \quad x\in (-\infty,t_{i-1}].
\end{align*}
When $x\in(t_{i-1},t_i]$, the fact that $(t_{i-1}-x)_+^2 = 0,
(t_{i}-x)_+^2 = (t_{i}-x)^2, (t_{i+1}-x)_+^2 = (t_{i+1}-x)^2$ and
$(t_{i+2}-x)_+^2 = (t_{i+2}-x)^2$ imply
\begin{align*}
  &(t_{i+2} - t_{i-1})[t_{i-1},t_i,t_{i+1},t_{i+2}](t - x)_+^2\\
  &=\frac{(t_{i+2}-x)^2-(t_{i+1}-x)^2}{(t_{i+2} - t_{i})(t_{i+2} -
    t_{i+1})} -\frac{(t_{i+1}-x)^2-(t_{i}-x)^2}{(t_{i+2} -
    t_{i})(t_{i+1} - t_{i})}\\
  &\ -\frac{(t_{i+1}-x)^2-(t_{i}-x)^2}{(t_{i+1} - t_{i-1})(t_{i+1} -
    t_{i})} +\frac{(t_{i}-x)^2}{(t_{i+1} - t_{i-1})(t_{i} -
    t_{i-1})}\\
  &= \frac{t_{i+2}+t_{i+1}+2x}{t_{i+2}-t_{i}} -
    \frac{t_{i+1}+t_{i}+2x}{t_{i+2}-t_{i}}\\
  &\ -\frac{t_{i+1}+t_{i}+2x}{t_{i+1}-t_{i-1}}  +\frac{(t_{i}-x)^2}{(t_{i+1} - t_{i-1})(t_{i} -
    t_{i-1})}\\
  &= \frac{(t_{i-1}-x)^2}{(t_{i+1} - t_{i-1})(t_{i} -
    t_{i-1})} = B_i^2(x),\quad  x\in (t_{i-1},t_i].
\end{align*}
Similarly, when $x\in(t_i,t_{i+1}]$, the fact that $(t_{i-1}-x)_+^2 = 0,
(t_{i}-x)_+^2 = 0, (t_{i+1}-x)_+^2 = (t_{i+1}-x)^2$ and
$(t_{i+2}-x)_+^2 = (t_{i+2}-x)^2$ imply
\begin{align*}
  &(t_{i+2} - t_{i-1})[t_{i-1},t_i,t_{i+1},t_{i+2}](t - x)_+^2\\
  &=\frac{(t_{i+2}-x)^2-(t_{i+1}-x)^2}{(t_{i+2} - t_{i})(t_{i+2} -
    t_{i+1})}\\
  &\ -\frac{(t_{i+1}-x)^2}{(t_{i+2} -
    t_{i})(t_{i+1} - t_{i})}\\
  &\ -\frac{(t_{i+1}-x)^2}{(t_{i+1} - t_{i-1})(t_{i+1} -
    t_{i})}\\
  &= \frac{(x-t_{i-1})(t_{i+1}-x)}{(t_{i+1}-t_{i-1})(t_{i+1}-t_i)} +\frac{(t_{i+2}-x)(x-t_i)}{(t_{i+2}-t_{i})(t_{i+1}-t_i)}\\
  &\ = B_i^2(x),\quad x\in (t_{i},t_{i+1}].
\end{align*}
When $x\in(t_{i+1},t_{i+2}]$, the fact that $(t_{i-1}-x)_+^2 = 0,
(t_{i}-x)_+^2 = 0, (t_{i+1}-x)_+^2 = 0$ and
$(t_{i+2}-x)_+^2 = (t_{i+2}-x)^2$ imply
\begin{align*}
  &(t_{i+2} - t_{i-1})[t_{i-1},t_i,t_{i+1},t_{i+2}](t - x)_+^2\\
  &=\frac{(t_{i+2}-x)^2}{(t_{i+2} - t_{i})(t_{i+2} -
    t_{i+1})} = B_i^2(x),\quad x\in (t_{i+1},t_{i+2}].
\end{align*}
Lastly, when $x\in(t_{i+2},\infty)$, all terms equal to 0 and the
conclusion clearly holds.\\
In conclusion, we have verified
\begin{align*}
  (t_{i+2} - t_{i-1})[t_{i-1},t_i,t_{i+1},t_{i+2}](t - x)_+^2 = B_i^2.
\end{align*}
    \end{proof}
  \item
    % 问题7
    \begin{proof}
      By Theorem 3.34, we integrate on both sides and get
\begin{align*}
  0 &= B_i^n(t_{i+n}) - B_i^n(t_{i-1}) = \int_{t_{i-1}}^{t_{i+n}}
  \frac{\mathrm{d} }{\mathrm{d} x} B_i^n(x)dx\\
  &= \frac{n\int_{t_{i-1}}^{t_{i+n}}B_i^{n-1}(x)dx}{t_{i+n-1}-t_{i-1}}
    -
    \frac{n\int_{t_{i-1}}^{t_{i+n}}B_{i+1}^{n-1}(x)dx}{t_{i+n}-t_{i}}\\
  &=\frac{n\int_{t_{i-1}}^{t_{i+n-1}}B_i^{n-1}(x)dx}{t_{i+n-1}-t_{i-1}}
    -
    \frac{n\int_{t_{i}}^{t_{i+n}}B_{i+1}^{n-1}(x)dx}{t_{i+n}-t_{i}},
\end{align*}
where the first and last equation follow from the fact that the support
of $B_i^n$ is $[t_{i-1},t_{i+n}]$, and the second equation from
fundamental theorem of calculus.\par
Hence we have
\begin{equation*}
\frac{\int_{t_{i-1}}^{t_{i+n-1}}B_i^{n-1}(x)dx}{t_{i+n-1}-t_{i-1}}
    =
    \frac{\int_{t_{i}}^{t_{i+n}}B_{i+1}^{n-1}(x)dx}{t_{i+n}-t_{i}}.
\end{equation*}
By induction,
\begin{align*}
  \frac{\int_{t_{i-1}}^{t_{i+n-1}}B_i^{n-1}(x)dx}{t_{i+n-1}-t_{i-1}} =
  s(n) = \frac{1}{n},\quad \forall i \in \mathbb{Z},
\end{align*}
where $s(n)$ is independent of $i$. Therefore, the scaled integral of a B-spline $B_i^n(x)$ over its
support is independent of its index $i$.
    \end{proof}
  \item
    % 问题8
    \begin{proof}
      \begin{enumerate}
      \item
        Since we observe that
        \begin{align*}
  &[x_i,x_{i+1},x_{i+2}]x^4\\
  &=\frac{[x_{i+1},x_{i+2}]x^4-[x_i,x_{i+1}]x^4}{x_{i+2}-x_i}\\
  &=\frac{x_{i+2}^4 - x_{i+1}^4}{(x_{i+2}-x_i)(x_{i+2}-x_{i+1})} - \frac{x_{i+1}^4 - x_{i}^4}{(x_{i+2}-x_i)(x_{i+1}-x_{i})}\\
  &=\frac{(x_{i+2}^2+x_{i+1}^2)(x_{i+2}+x_{i+1})}{x_{i+2}-x_i} - \frac{(x_{i+1}^2+x_{i}^2)(x_{i+1}+x_{i})}{x_{i+2}-x_i} \\
  &=x_{i+2}^2+x_{i+2}x_{i+1}+x_{i+2}x_i + x_{i+1}^2+x_{i}^2+x_{i+1}x_i\\
  &=\tau_2(x_i,x_{i+1},x_{i+2}),    
\end{align*}
        which verifies this theorem for $m=4$ and $n=2$.
      \item
        For $n = 0$, there clearly exists $\tau_m(x_i)= [x_i]x^m$. Hence the induction basis holds. Now assume that the induction hypothesis holds.\par
Considering the fact that
\begin{equation*}
  (x_n - x_1)\tau_m(x_1,\cdots,x_n) = \tau_{m+1}(x_2,\cdots,x_n) - \tau_{m+1}(x_1,\cdots,x_{n-1}),
\end{equation*}
which can be easily implied by the recursive relation on complete
symmetric polynomials. Then 
\begin{align*}
  &\tau_{m-n}(x_i,x_{i+1},\cdots,x_{i+n})\\
  &=\frac{\tau_{m-n+1}(x_{i+1},\cdots,x_{i+n}) - \tau_{m-n+1}(x_i,\cdots,x_{i+n-1})}{x_{i+n} - x_i} \\
  &=\frac{[x_{i+1},\cdots,x_{i+n}]x^m-[x_i,\cdots,x_{i+n-1}]x^m}{x_{i+n}
    - x_i}\\
  &=[x_i,x_{i+1},\cdots,x_{i+n}]x^m,
\end{align*}
which completes the inductive proof.
      \end{enumerate}
      \end{proof}
\end{enumerate}
\end{document}
